Modular Polynomial algorithm
What is the Modular Polynomial Algorithm?
Modular Polynomial Algorithm is a technique for performing polynomial arithmetic within a finite field, typically GF(p), where all operations are conducted modulo a prime number and a polynomial. It extends standard polynomial division to work within modular arithmetic, allowing complex polynomial manipulations while keeping values within a defined range.
Key Components:
1. Polynomials with coefficients in GF(p)
2. Modulus polynomial
3. Prime number p
4. Polynomial arithmetic rules
5. Reduction technique
Core Rules:
1. Perform polynomial operations
2. Reduce result using modulus polynomial
3. Keep coefficients within GF(p)
4. Maintain polynomial degree less than modulus degree
Example with GF(5) and Modulus x² + 1:
Multiplication:
• (3x + 2) * (4x + 1)
• 12x² + 3x + 8x + 2
• Reduce modulo x² + 1
• 12x² ≡ -12 (mod x² + 1)
• Final result: (3-12)x + (2+8) mod 5